
#define _BSD_SOURCE
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <errno.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>

#include "config.h"

#include "zbd-cache.h"
#include "log.h"
#include "hashtable.h"

#include "../algorithms-general.h"

extern struct cache_runtime cache_rt;
typedef uint64_t blockaddr_t ;
typedef int zoneid_t ;

#define MAXTRACEMAPLEN 2000000000

#ifndef LOOKAHEAD
# define LOOKAHEAD 1
#else 
# pragma message("LOOKAHEAD=#LOOKAHEAD")
#endif

//int TOPK;


#define OFFLINE
#ifdef OFFLINE
/******************* Reuse Interval Utils *******************/
#define MMOD 100000003 // 哈希表大质数(建议比DIFFER_BLOCK大)
#define DIFFER_BLOCK 500000000 // 出现过的不同的块数
#define MAX_ACCRSS_LEN 1000000000 // trace 长度

static int* Pages_Head; // MMAP -> Pages_Head[DIFFER_BLOCK]
static int* Pages_Nxt;  // MMAP -> Pages_Nxt[TRACE_LEN]
int Cursor;
typedef struct hash_translate{
    /*
    int head[MMOD+5] , <- malloc
        pre[DIFFER_BLOCK+5] , <- MMAP
        mapval[DIFFER_BLOCK+5] , <- MMAP
        tp ;
         
    blockaddr_t val[DIFFER_BLOCK+5] ;
    */
    int* head;
    int* pre;
    int* mapval;
    int tp ;
         
    blockaddr_t *val;
    int (*find) ( void* , blockaddr_t ) ;
    int (*insert) ( void* , blockaddr_t ) ;
} transtab_t ;
transtab_t transtab ;

static int transtab_t_find( void *t_ , blockaddr_t addr ) {
    transtab_t* t = t_ ;
    int id = addr % MMOD ;
    for( int i = t->head[id] ; i ; i = t->pre[i] ) {
        if( t->val[i] == addr ){
            return t->mapval[i] ;
        }
    }
    return -1 ;
}

static int transtab_t_insert( void *t_ , blockaddr_t addr ) {
    transtab_t *t = t_ ;
    int id = addr % MMOD ;
    ++t->tp  ;
    t->pre[t->tp] = t->head[id] ;
    t->head[id] = t->tp ;
    t->val[t->tp] = addr ;
    t->mapval[t->tp] = t->tp ;
    return 0 ;
}

static int ri_utils_init( blockaddr_t *addrs , int reqCnt ){

    /* 初始化opt哈希表 */
    char hashmap_dir[128];
    sprintf(hashmap_dir, "%s-MAXMINRIGREEDY-trace_%d", config_trace_hashmap_dir_prefix, STT.traceId);

    if(access(hashmap_dir, 0) == -1){
        mkdir(hashmap_dir, 0x0777);
    }


    transtab.head = (int*)calloc(MMOD + 5, sizeof(int));
    if(transtab.head == NULL){
        log_err_sac("[%s] error: %s\n", __func__, strerror(errno));
        exit(EXIT_FAILURE);
    }

    char hashfile_pre_path[128], hashfile_mapval_path[128], hashfile_val_path[128];
    sprintf(hashfile_pre_path, "%s/pre", hashmap_dir);
    sprintf(hashfile_mapval_path, "%s/mapval", hashmap_dir);
    sprintf(hashfile_val_path, "%s/val", hashmap_dir);

    int prefd, mapvalfd, valfd;
    prefd = open(hashfile_pre_path, O_RDWR | O_CREAT);
    mapvalfd = open(hashfile_mapval_path, O_RDWR | O_CREAT);
    valfd = open(hashfile_val_path, O_RDWR | O_CREAT);
    if ( prefd < 0 || mapvalfd < 0 || valfd < 0){
        log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    ftruncate(prefd, sizeof(int) * (DIFFER_BLOCK+5));
    ftruncate(mapvalfd, sizeof(int) * (DIFFER_BLOCK+5));
    ftruncate(valfd, sizeof(blockaddr_t) * (DIFFER_BLOCK+5));

    transtab.pre =      mmap(NULL, sizeof(int) * (DIFFER_BLOCK+5), PROT_READ | PROT_WRITE, MAP_SHARED, prefd, 0);
    transtab.mapval =   mmap(NULL, sizeof(int) * (DIFFER_BLOCK+5), PROT_READ | PROT_WRITE, MAP_SHARED, mapvalfd, 0);
    transtab.val =      mmap(NULL, sizeof(blockaddr_t) * (DIFFER_BLOCK+5), PROT_READ | PROT_WRITE, MAP_SHARED, valfd, 0);

    if (transtab.pre == (void *)-1 || transtab.mapval == (void *)-1 || transtab.val == (void *)-1)
    {
        log_err_sac("Create hashtabel mmap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    /* 初始化Pages_Head[] */
    char pageshead_path[128], pagesnxt_path[128];
    sprintf(pageshead_path, "%s/pageshead", hashmap_dir);
    sprintf(pagesnxt_path, "%s/pagesnxt", hashmap_dir);
    int pagesheadfd = open(pageshead_path, O_RDWR | O_CREAT); 
    int pagesnxtfd = open(pagesnxt_path, O_RDWR | O_CREAT); 
    ftruncate(pagesheadfd, sizeof(int) * DIFFER_BLOCK);
    ftruncate(pagesnxtfd, sizeof(int) * reqCnt);

    Pages_Head = mmap(NULL, sizeof(int) * DIFFER_BLOCK, PROT_READ | PROT_WRITE, MAP_SHARED, pagesheadfd, 0);
    Pages_Nxt =  mmap(NULL, sizeof(int) * reqCnt, PROT_READ | PROT_WRITE, MAP_SHARED, pagesnxtfd, 0); 
    if (Pages_Head == (void *)-1 || Pages_Nxt == (void *)-1)
    {
        log_err_sac("Create hashtabel mmap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    transtab.tp = 0 ;
    transtab.find = transtab_t_find ;
    transtab.insert = transtab_t_insert ;
    //memset( transtab.head , 0 , sizeof( transtab.head ) ) ; // calloc

    // head should init to be +inf , so that next[last] = inf 
    int tp =  reqCnt;
    for( int i = 0 ; i < DIFFER_BLOCK ; i ++ ){
        Pages_Head[i] = MAXTRACEMAPLEN ;
    }
    Cursor = -1 ; // cursor position of access list
    
    for( int i = reqCnt - 1 ; i >= 0 ; i -- ){
        int mappedaddr = transtab.find( &transtab , addrs[i] ) ;
        if( mappedaddr < 0 ){
            transtab.insert( &transtab , addrs[i] ) ;
            mappedaddr = transtab.find( &transtab , addrs[i] ) ;
        }
        Pages_Nxt[--tp] = Pages_Head[mappedaddr] ;
        Pages_Head[mappedaddr] = tp ;
    }


    return 0;
}

static int ri_utils_movnext( blockaddr_t addr ){
    int mappedaddr = transtab.find( &transtab , addr ) ;
    if( Pages_Head[mappedaddr] != Cursor + 1 ){ // check if the input addr match the saved info
        log_err_sac("%s: error\n", __func__);
        exit(EXIT_FAILURE);
    }
    Pages_Head[mappedaddr] = Pages_Nxt[ Pages_Head[mappedaddr] ] ;
    Cursor ++ ;
    return 0 ; // OK
}

static int query_now_ri( blockaddr_t addr ){
    int mappedaddr = transtab.find( &transtab , addr ) ;
    return Pages_Head[mappedaddr] - Cursor ;    
}

/******************* Reuse Interval Utils *******************/
#endif

#define RECALL_THRESHOLD (STT.n_cache_pages * STT.ribound / 10 + STT.n_cache_pages)

/* zbd-cache.h */
struct cache_page;
extern struct zbd_zone *zones_collection;
extern struct cache_runtime cache_rt;

extern int RMW(uint32_t zoneId, uint64_t from_blk, uint64_t to_blk);

/* most-specified objs */
struct page_payload
{
    uint64_t checked_round; // Abort 弃用
};

static uint64_t global_evic_round;

/* cache out */
static int eiri_get_zone_out();
static int compareByReleaseForMiss(const void *a, const void *b);

struct zoneFutureStat
{
    int zoneId;
    int releaseCnt;
    int releaseForMiss;
    struct zoneFutureStat *pre, *next;

    int increamentalBlks;
};

struct zfsIndex
{
    struct zoneFutureStat *zfs;
};

struct zfsMap
{
    struct zfsIndex* idxs;
    struct zoneFutureStat* zfsArr;    
    struct zoneFutureStat* head, * tail;
    int distance;
    int missesInRound;

    uint32_t tracePos;
    int candidateZoneId;
    struct hash_table * incHashtb;
};

extern struct hash_table *CacheBlkHashtb;
static struct zfsMap ZfsMapStack[LOOKAHEAD + 1];
struct EvictionInterval
{
    uint32_t zoneId;
    int ei;
};
struct EvictionInterval EvictionSerial [LOOKAHEAD];

static int CurrentRound = LOOKAHEAD; 

uint64_t *TraceMAP;

// Functions for zfs. 
static void zfs_insertfront(struct zoneFutureStat * zfs, struct zoneFutureStat * target);
static int searchNextOneTopK(int thisRound, int inTopK);
static int init_zfsMap(int level);
static void free_zfsMap(int level);
static int isMissInAllRoundLevel(uint64_t tg_blk, int curRound);


int eiri_init()
{
    /* init page priv field. */
    struct cache_page *page = cache_rt.pages;
    for (uint64_t i = 0; i < STT.n_cache_pages; page++, i++)
    {
        page->priv = calloc(1, sizeof(struct page_payload));
        if (!page->priv)
            return -1;
    }

    global_evic_round = 0;

    char tracemap[128];
    sprintf(tracemap, "%s_%d", config_trace_seq_mmap_file_prefix, STT.traceId);
    int maxMapReq = MAXTRACEMAPLEN;
    
    int tracemapfd = open(tracemap, O_RDONLY);
    if (tracemapfd < 0)
    {
        // open trace file
        
        if ((tracemapfd = open(tracemap, O_RDWR | O_CREAT)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
        ftruncate(tracemapfd, sizeof(uint64_t) * maxMapReq);

        TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ | PROT_WRITE, MAP_SHARED, tracemapfd, 0);
        if (TraceMAP == (void *)-1)
        {
            log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }

        FILE *trace = fopen(TRACE_FILES[STT.traceId], "rt");
        if (trace == NULL)
        {
            exit(EXIT_FAILURE);
        };

        char action;
        uint64_t tg_blk;
        int mask;
        uint64_t *wrtReq = TraceMAP;
        uint64_t scanReqCnt = 0;
        while (!feof(trace)) // && scanReqCnt < STT.presetReq)
        {
            int ret;
#ifdef TRACE_SYSTOR17
            ret = fscanf(trace, "%c %d %lu\n", &action, &mask, &tg_blk);
#else
            ret = fscanf(trace, "%d %d %lu\n", &action, &mask, &tg_blk);
#endif

            if (ret < 0)
            {
                log_err_sac("error while reading trace file.");
                break;
            }

#ifdef TRACE_SYSTOR17
            tg_blk /= BLKSIZE;
#endif
            tg_blk += STT.start_Blkoff;

            if (action == ACT_WRITE && (STT.workload_mode & 0x02))
            {
                if ((tg_blk / N_ZONEBLK) > N_ZONES)
                {
                    log_info_sac("[warning] func:%s, target block overflow. \n", __func__);
                    continue;
                }

                *wrtReq = tg_blk;
                wrtReq++;
                scanReqCnt++;
            }
        }

        fclose(trace);
        msync(TraceMAP, sizeof(uint64_t) * maxMapReq, MS_SYNC);
        munmap(TraceMAP, sizeof(uint64_t) * maxMapReq);
        close(tracemapfd);
        // reopen
        if ((tracemapfd = open(tracemap, O_RDONLY)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
    }

    TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ, MAP_SHARED, tracemapfd, 0);
    if (TraceMAP == (void *)-1)
    {
        log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    return ri_utils_init(TraceMAP, STT.presetReq + (4*STT.n_cache_pages));
}

int eiri_login(struct cache_page *page, int op)
{
    // struct page_payload * p = (struct page_payload *)page->priv;
    // p->checked_round = 0;
    ri_utils_movnext(page->tg_blk);
    return 0;
}

int eiri_logout(struct cache_page *page, int op)
{
    return 0;
}

int eiri_hit(struct cache_page *page, int op)
{
    ri_utils_movnext(page->tg_blk);
    return 0;
}

int eiri_writeback_privi(int type)
{
    int ret, cnt = 0;
    struct page_payload *payload;

    if (type == FOR_READ)
        goto EVICT_CLEAN;
    else if (type == FOR_WRITE || type == FOR_UNKNOWN)
        goto EVICT_DIRTY;
    else
    {
        log_err_sac("[%s] error: MOST cache algorithm needs to be told eviction page type. \n", __func__);
        exit(EXIT_FAILURE);
    }

EVICT_CLEAN:
    log_err_sac("This offline algorithm doesn't support evicting clean block.");
    exit(EXIT_FAILURE);

EVICT_DIRTY:
    global_evic_round++;
    ret = eiri_get_zone_out();
    return ret;
}

static int searchMaxEI_DFS(int thisRound, struct EvictionInterval* retBestEvictSerial, int* sumEI)
{
    if(thisRound == 0)
        return 0;
    
    if(thisRound > LOOKAHEAD){
        *sumEI = 0;
        return 0;
    }

    int maxEIRI = -1;
    // duplicate curZfsArray
    //init_zfsMap(thisRound);
    //struct zfsMap* myMap = &ZfsMapStack[thisRound];
    //TOPK = myMap->distance;

    // 统计每个page的RI，在阈值内的RI的page计入recall统计
    double * recallblks = calloc(N_ZONES, sizeof(double));
    struct cache_page* page = cache_rt.pages;
    for (uint64_t i = 0; i < STT.n_cache_pages; page++, i++)
    {
        int ri = query_now_ri(page->tg_blk);
        if(ri > STT.ribound){
            ri = STT.ribound;
        }

        double weight = 1 - ((double)ri / STT.ribound);
        recallblks[page->belong_zoneId] += weight;

        // if(ri <= STT.ribound){
        //     recallblks[page->belong_zoneId] ++;
        // }
    }

    // continue run trace...
    // struct EvictionInterval* subBestEvictSerial = calloc(LOOKAHEAD - thisRound, sizeof(struct EvictionInterval));
    // int candidate_zoneId;
    // while((candidate_zoneId = searchNextOneTopK(thisRound, TOPK)) >= 0){
        
    //             //int ei = myMap->tracePos - ZfsMapStack[thisRound - 1].tracePos;

    //     myMap->candidateZoneId = candidate_zoneId;
    //     //searchMaxEI_DFS(thisRound + 1, subBestEvictSerial, &subMaxEI);

        
    //     //ei += subMaxEI;
    //     int eiri = zones_collection[candidate_zoneId].cblks;
    //     eiri -= recallblks[candidate_zoneId];
        
    //     if(eiri > maxEIRI){
    //         maxEIRI = eiri; 
    //         retBestEvictSerial[0].zoneId = myMap->candidateZoneId;
    //         retBestEvictSerial[0].ei = eiri;
            
    //         memcpy(&retBestEvictSerial[1], subBestEvictSerial, sizeof(struct EvictionInterval)* (LOOKAHEAD - thisRound));
    //         // update EvictionSerial [LOOKAHEAD];
    //     }
            
    // }

    for(int i = 0; i < N_ZONES; i ++){
        if(zones_collection[i].cblks == 0){continue;}
        int eiri = zones_collection[i].cblks;
        eiri -= recallblks[i];
        if(eiri > maxEIRI){
            maxEIRI = eiri; 
            retBestEvictSerial[0].zoneId = i;
            retBestEvictSerial[0].ei = eiri;
            // update EvictionSerial [LOOKAHEAD];
        }
    }
    
    *sumEI = maxEIRI;
    //free(subBestEvictSerial);
    //free_zfsMap(thisRound);
    free(recallblks);
    return maxEIRI; 
}

static int searchNextOneTopK(int thisRound, int inTopK){
    if(ZfsMapStack[thisRound].distance < 0)
        return ZfsMapStack[thisRound].distance;
    
    // build the map->tail zone eviction interval state
    int retZoneId = -1;
    struct zfsMap * myMap = &ZfsMapStack[thisRound];

    int tgDist = myMap->distance >= inTopK ? inTopK - 1 : myMap->distance;
    uint64_t* wrtTgtBlk = TraceMAP + myMap->tracePos;

    // if(myMap->missesInRound > myMap->tail->releaseForMiss){
    //     // wrong 
    //     log_err_sac("error");
    //     exit(EXIT_FAILURE);
    // }

    while(myMap->missesInRound > myMap->tail->releaseForMiss){
        if(myMap->distance == tgDist){
            retZoneId = myMap->tail->zoneId;
            myMap->tail = myMap->tail->pre;
            myMap->distance --;
            return retZoneId;
        }

        myMap->tail = myMap->tail->pre;
        myMap->distance --;
    }


    // find the next one in TopK
    while(myMap->tracePos < MAXTRACEMAPLEN){
        // run trace and tune the zfs ranking 
        int missed = isMissInAllRoundLevel(*wrtTgtBlk, thisRound);
        if(missed){
            myMap->missesInRound ++;

            uint32_t belong_zoneId = *wrtTgtBlk / N_ZONEBLK;
            struct zoneFutureStat * zfs = myMap->idxs[belong_zoneId].zfs;

            zfs->increamentalBlks ++;

            // Add to map->incremental hashmap
            HashTab_Insert(myMap->incHashtb, *wrtTgtBlk,  myMap->tracePos); 
            
            // tuning the zfs ranked position in zfsArr
            if(zfs->releaseCnt >0){
                zfs->releaseForMiss ++;

                // 1) find the inserted position
                struct zoneFutureStat *insert_zfs = zfs;
                while (insert_zfs->pre != NULL && zfs->releaseForMiss > insert_zfs->pre->releaseForMiss)
                {
                    insert_zfs = insert_zfs->pre;
                }

                // 2) move
                if(insert_zfs != zfs && zfs == myMap->tail){
                    myMap->tail = myMap->tail->pre;
                }
                zfs_insertfront(zfs, insert_zfs);
                if(myMap->head->pre == zfs){
                    myMap->head = zfs;
                }
            }

        } else {
            int hit = 1;    
        }
        
        // check the tail zone filled and move the tail pointer
        while(myMap->missesInRound > myMap->tail->releaseForMiss){
            if(myMap->distance == tgDist){
                retZoneId = myMap->tail->zoneId;
                myMap->tail = myMap->tail->pre;
                myMap->distance --;
                myMap->tracePos ++;
                return retZoneId;
            }
            myMap->tail = myMap->tail->pre;
            myMap->distance --;
        }

        wrtTgtBlk ++;
        myMap->tracePos ++;
    }


    // Reach the trace length
    // while(myMap->distance > tgDist){
    //     myMap->tail = myMap->tail->pre;
    //     myMap->distance--;
    // }

    // retZoneId = myMap->tail->zoneId;
    // myMap->tail = myMap->tail->pre;
    // myMap->distance--;
    myMap->distance = -1;
    retZoneId = myMap->head->zoneId;
    return retZoneId;
}


static int eiri_get_zone_out()
{
    
    uint32_t from = 0, to = N_ZONEBLK - 1;

    if(CurrentRound == LOOKAHEAD){
        CurrentRound = 0;

        int maxSumEI;
        init_zfsMap(0);
        searchMaxEI_DFS(1, EvictionSerial, &maxSumEI);
    }

    int best_zoneId = EvictionSerial[CurrentRound].zoneId;

    // output write amplification.
    struct zbd_zone* z = zones_collection + best_zoneId;
    uint32_t rmw_scope = N_ZONEBLK - from;
    double wa = (double)rmw_scope / z->cblks_wtr;
    int canWalkTo = STT.resetReqSeq + STT.reqcnt_w + EvictionSerial[CurrentRound].ei - 1;

    log_info_sac("[%s] Zone[%d] WA: %.2f (%u/%u); EIRI: %ld\n", 
    __func__, z->zoneId, wa, rmw_scope, z->cblks_wtr, EvictionSerial[CurrentRound].ei);

    // RMW
    RMW(best_zoneId, from, to);

    CurrentRound ++;
    return best_zoneId;
}

static int compareByReleaseForMiss(const void *a, const void *b) //用来做比较的函数。
{
    return ((struct zoneFutureStat *)a)->releaseForMiss < ((struct zoneFutureStat *)b)->releaseForMiss;
}

static int isMissInAllRoundLevel(uint64_t tg_blk, int curRound){
    //log_info_sac("\ncheck hashtb: tgblk=%ld --> ", tg_blk);
    int i;
    int belong_zoneId = tg_blk / N_ZONES;
    for(i = curRound; i >= 0; i--){
        struct zfsMap * levelMap = &ZfsMapStack[i];
        if(i != curRound && belong_zoneId == levelMap->candidateZoneId){
            //log_info_sac("missed by ignore in level [%d]", i);
            return 1; // must miss
        }

        if(HashTab_Lookup(levelMap->incHashtb, tg_blk, NULL) >= 0){
            // hit
            //log_info_sac("hit in level [%d].", i);
            return 0;
        }
    }

    //log_info_sac("missed in all levels.");
    return 1; // missed
}



static void zfs_insertfront(struct zoneFutureStat * zfs, struct zoneFutureStat * target){
    if(target == NULL || zfs == NULL)
        return;

    if(target == zfs){
        return;
    }

    // take off zfs
    if(zfs->pre != NULL){ zfs->pre->next = zfs->next; }
    if(zfs->next != NULL) { zfs->next->pre = zfs->pre; }

    // insert in front of the target. 

    zfs->pre = target->pre;
    zfs->next = target;
    if (target->pre != NULL)
    {
        target->pre->next = zfs;
    }
    target->pre = zfs;
}

static int init_zfsMap(int level){
    if(level == 0){
        struct zfsMap* map = &ZfsMapStack[0];
        map->idxs = NULL; // do not need to set idx
        map->tracePos = STT.resetReqSeq + STT.reqcnt_w ;
        map->incHashtb = CacheBlkHashtb;
        map->candidateZoneId = -1;
        map->head = map->tail = NULL;
        map->distance = 0;
        map->zfsArr = malloc(sizeof(struct zoneFutureStat) * N_ZONES);
        if(map->zfsArr == NULL){
            log_err_sac("%s: error", __func__);
            exit(EXIT_FAILURE);
        }

        struct zbd_zone *z = zones_collection;
        struct zoneFutureStat *zfs = map->zfsArr;
        for (int i = 0; i < N_ZONES; i++, z++, zfs++)
        {
            zfs->zoneId = z->zoneId;
            zfs->releaseCnt = z->cblks_wtr;
            zfs->releaseForMiss = z->cblks_wtr;
            zfs->increamentalBlks = 0;
        }

        return 0;
    }

    struct zfsMap* map = &ZfsMapStack[level];
    struct zfsMap* base = &ZfsMapStack[level - 1];
    map->tracePos = base->tracePos;
    map->zfsArr = malloc(sizeof(struct zoneFutureStat) * N_ZONES);
    map->idxs = malloc(sizeof(struct zfsIndex) * N_ZONES);
    if(map->zfsArr == NULL || map->idxs == NULL){
        log_err_sac("%s: error", __func__);
        exit(EXIT_FAILURE);
    }

    struct zoneFutureStat* baseZfs = base->zfsArr;
    struct zoneFutureStat* genZfs = map->zfsArr;
    for(int i = 0; i < N_ZONES; i++, baseZfs++, genZfs++){
        genZfs->zoneId = baseZfs->zoneId;
        genZfs->releaseForMiss = 
            genZfs->releaseCnt = baseZfs->releaseCnt + baseZfs->increamentalBlks;
        genZfs->increamentalBlks = 0;

        // 剔除上一轮此候选Zone的配置
        if(genZfs->zoneId == base->candidateZoneId){
            genZfs->releaseForMiss = genZfs->releaseCnt = 0;
        }
    }



    qsort(map->zfsArr, N_ZONES, sizeof(struct zoneFutureStat), compareByReleaseForMiss);
    
    // link the zfsArr and build their indexes.
    genZfs = map->zfsArr;
    struct zoneFutureStat *pre = NULL;
    for(int i = 0; i < N_ZONES; i++, genZfs ++)
    {
        genZfs->pre = pre;
        if(pre != NULL)
            pre->next = genZfs;
        
        pre = genZfs;

        map->idxs[genZfs->zoneId].zfs = genZfs;
    }
    pre->next = NULL;

    map->head = map->zfsArr;
    map->tail = map->zfsArr + N_ZONES - 1;
    map->distance = N_ZONES - 1;
    map->missesInRound = 0;
    while(map->tail != NULL && map->tail->releaseForMiss == 0){
        map->tail = map->tail->pre;
        map->distance --;
    }

    HashTab_crt(STT.n_cache_pages, &map->incHashtb);
    map->candidateZoneId = -1;

    return 0;
}

static void free_zfsMap(int level){
    struct zfsMap* map = &ZfsMapStack[level];
    free(map->idxs);
    free(map->zfsArr);
    HashTab_free(map->incHashtb);
    map->candidateZoneId = -1;
    map->tracePos  = 0;
}